Grokking Algorithm Complexity and Big-O
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Course Overview
Basics of Algorithm Analysis
Introduction to Algorithm Analysis
Measuring Efficiency
Functions and Their Growth Rates
Asymptotic Notations
Overview of Asymptotic Analysis
Big-O Notation (O-notation)
Big-Omega Notation (Ω-notation)
Big-Theta Notation (Θ-notation)
Little-o and Little-omega Notations
Comparing Asymptotic Notations
Time Complexity Analysis
Understanding Time Complexity
Analyzing Control Structures
Analyzing Simple Algorithms
Best, Worst, and Average Cases
Constant Time: O(1)
Linear Time: O(n)
Quadratic Time: O(n²)
Quiz
Space Complexity Analysis
Understanding Space Complexity
Analyzing Space Complexity of Algorithms
Constant Space: O(1)
Linear Space: O(n)
Quadratic Space: O(n²)
Quiz
Analyzing Recursive Algorithms
Introduction to Recursion
Recursion Tree Method
Recurrence Relation Method
Master Theorem Method
Space Complexity Analysis of Recursive Algorithm
Logarithmic Time and Space: O(log n)
Linearithmic Time: O(n log n)
Exponential Time and Space: O(2ⁿ)
Quiz
Data Structures and Complexity Analysis
Array
Linked List
Hash Table and Set
Stack and Queue
Binary Search Tree
Quiz
Practical Applications and Case Studies
Sorting Algorithms
Graph Algorithms
Dynamic Programming Algorithms
Coding Interview Problems
Trade-offs in Algorithm Design
Coding Interview Problems

In this lesson, we will explore three complex coding interview problems that cover a variety of algorithms and problem-solving techniques. We’ll look at problems involving sorting, tree traversal, and greedy algorithms. These examples are designed to help you understand how to approach different types of problems in competitive programming and improve your problem-solving skills.

1. Problem: Merge Intervals

Problem Statement: Given an array of intervals where intervals[i] = [start, end], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Java
Saved to Cloud

. . . .

Time Complexity for Merge Intervals Algorithm

  1. Sorting Step:

    • The first operation in the code is sorting the intervals array based on the start times.
    • Time Complexity of Sorting: The sorting step takes , where n is the number of intervals. This is due to the use of a comparison-based sorting algorithm such as Timsort.
  2. Merging Step:

    • The for-loop iterates through each interval exactly once, performing operations for each iteration to check for overlaps and merge intervals if necessary.
    • Time Complexity of the Loop: The loop runs in because it processes each of the n intervals once.

Overall Time Complexity:

  • The overall time complexity is dominated by the sorting step:

Space Complexity for Merge Intervals Algorithm

  1. Space for Sorting:

    • The sorting has a space complexity of due to the use of in-place sorting for primitive types.
  2. Auxiliary Space for Merging:

    • The merged list is used to store the merged intervals. In the worst case, if there are no overlapping intervals, the list will store all n intervals, resulting in space.
  3. Output Array:

    • The toArray() method creates a new array to return the result, which also takes space.

Overall Space Complexity:

  • The total space complexity is: The primary contributor to space usage is the List used for storing merged intervals and the output array.

2. Problem: Maximum Path Sum in a Binary Tree

Problem Statement: Given a non-empty binary tree, find the maximum path sum. The path may start and end at any node in the tree.

Java
Saved to Cloud

. . . .

Time Complexity for Maximum Path Sum in a Binary Tree

  1. Recursive Calls:

    • The function findMaxPath(TreeNode node) is called recursively for each node in the tree.
    • Number of Calls: Each node in the tree is visited exactly once during the traversal.
    • Overall Time Complexity: , where n is the number of nodes in the binary tree. Each node is processed once, making the traversal linear in relation to the number of nodes.
  2. Operations per Node:

    • For each node, the following operations are performed:
      • Calculating leftMax and rightMax using recursive calls → for each operation.
      • Calculating maxSum by comparing and updating → .
      • Returning the result for the current node → .
    • The total work done at each node is constant, , so the time complexity remains as each node is visited once.

Space Complexity for Maximum Path Sum in a Binary Tree

  1. Recursive Call Stack:

    • The space complexity due to recursion depends on the maximum depth of the tree (i.e., the height h).
    • Balanced Tree: For a balanced tree, the height is .
    • Unbalanced Tree (Skewed): In the worst case (e.g., a tree that behaves like a linked list), the height is .
  2. Auxiliary Space:

    • No additional data structures are used that depend on the size of the input, aside from the recursion stack.

Overall Space Complexity:

  • Best Case (Balanced Tree):
  • Worst Case (Unbalanced Tree):

3. Problem: Fractional Knapsack (Greedy Algorithm)

Problem Statement: Given the weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. You can take fractions of items.

Java
Saved to Cloud

. . . .

Time Complexity for Fractional Knapsack Problem

  1. Sorting Step:

    • The items array is sorted based on the value-to-weight ratio in descending order.
    • Time Complexity of Sorting: Sorting the array of n items takes due to the use of a comparison-based sorting algorithm (Timsort in Java's Arrays.sort()).
  2. Iterating Through Items:

    • The loop iterates over each of the n items once to add them or fractions of them to the knapsack.
    • Time Complexity of Loop: .

Overall Time Complexity:

  • The overall time complexity is:

The sorting step dominates the runtime.

Space Complexity for Fractional Knapsack Problem

  1. Auxiliary Space:

    • The space used for sorting is due to the in-place sorting algorithm.
    • No additional data structures are used, apart from a few variables to store the total value and the capacity W.
  2. Space for Input:

    • The input items array does not count toward auxiliary space complexity as it is provided as input and not created within the function.

Overall Space Complexity:

  • The total space complexity is: for auxiliary space, as the algorithm does not require additional data structures that scale with input size beyond sorting space.
Dynamic Programming Algorithms
Trade-offs in Algorithm Design
Mark as Completed

On this page

  1. Problem: Merge Intervals

Time Complexity for Merge Intervals Algorithm

Space Complexity for Merge Intervals Algorithm

  1. Problem: Maximum Path Sum in a Binary Tree

Time Complexity for Maximum Path Sum in a Binary Tree

Space Complexity for Maximum Path Sum in a Binary Tree

  1. Problem: Fractional Knapsack (Greedy Algorithm)

Time Complexity for Fractional Knapsack Problem

Space Complexity for Fractional Knapsack Problem